# -*- mode: snippet -*-
# name: primefacto
# key: primefacto
# --
map<ll, int> prime_facto(ll n) {
  map<ll, int> res;
  for (ll i = 2; i <= n / i; ++i) {
    while (n % i == 0) {
      res[i]++;
      n /= i;
    }
  }
  if (n > 1) res[n]++;
  
  return res;
}

